/*
 * @lc app=leetcode.cn id=842 lang=javascript
 *
 * [842] 将数组拆分成斐波那契序列
 */

// @lc code=start
/**
 * @param {string} S
 * @return {number[]}
 */
var splitIntoFibonacci = function (S) {
  const result = [];
  const size = S.length;
  backtrack(result, S, size, 0);
  return result;

  function backtrack(result, S, size, index) {
    if (index === size) {
      return result.length >= 3;
    }
    let preVal = 0;

    for (let i = index; i < size; i++) {
      if (S[index] === '0' && i > index) {
        break;
      }
      preVal = preVal * 10 + parseInt(S[i]);
      if (preVal > 2 ** 31 - 1) {
        break;
      }
      let resultSize = result.length;
      if (resultSize >= 2) {
        let sum = result[resultSize - 1] + result[resultSize - 2];
        if (preVal > sum) {
          break;
        } else if (preVal < sum) {
          continue;
        }
      }
      result.push(preVal);
      if (backtrack(result, S, size, i + 1)) {
        return true;
      } else {
        result.pop();
      }
    }

    return false;
  }
};
// @lc code=end
